package com.krarl;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    LinkedList<Integer> path = new LinkedList<>();//使用链表存放符合条件的结果
    List<List<Integer>> result = new ArrayList<>();//使用二位整型列表存放结果集
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(n , k , 1, 0);
        return result;
    }

    private void backTracking(int n, int k, int startIndex, int sum) {

        if (sum > n) return; //剪枝操作


        if (path.size() > k) return;

        if (sum == n && path.size() == k) {
            result.add(new ArrayList<>(path));
            return; //如果path.size() == k 但sum != targetSum 直接返回
        }

        for(int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            backTracking(n,k, i + 1, sum); // 注意i+1调整startIndex

            sum -= i; //回溯
            path.removeLast();//回溯
        }
    }
};


public class TestCombinationSum3 {
    public static void main(String[] args) {
        solution solutionInstance = new solution();

        // Test Case 1
        int k1 = 3;
        int n1 = 7;
        System.out.println("Test Case 1:");
        List<List<Integer>> result1 = solutionInstance.combinationSum3(k1, n1);
        printResult(result1);

        // Test Case 2
        int k2 = 3;
        int n2 = 9;
        System.out.println("\nTest Case 2:");
        List<List<Integer>> result2 = solutionInstance.combinationSum3(k2, n2);
        printResult(result2);

        // Add more test cases as needed
    }

    private static void printResult(List<List<Integer>> result) {
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }
}

